package com.qrpcw.algorithms;

import java.util.ArrayList;
import java.util.Arrays;

public class BucketSortInt {

	public static void main(String[] args) {
		int[] data = GenerateRandomNumber.intNumbers(5000000);
		BucketSortInt  test = new BucketSortInt();
		System.out.println(Arrays.toString(test.concatenate(test.bucketSort(data))));
	}
	
	public ArrayList<ArrayList<Integer>> bucketSort(int[] A){
		int n = 901;
		ArrayList<ArrayList<Integer>> B = new ArrayList<ArrayList<Integer>>(n);
		for(int i=0; i<n; i++){
			B.add(i,new ArrayList<Integer>());
		} // let B[0~n-1] be a new array
		for(int i =0; i<n; i++){   
            int t = A[i]; //Bucket per number
            B.get(t).add(A[i]); 
        } //insert A[i] to B[floor(n*A[i])]
		return B;
	}
	
	//concatenate the lists B[1],B[2] ~ B[n-1] together in order
	public int[] concatenate(ArrayList<ArrayList<Integer>> b){
		int[] result = new int[b.size()];
		int counter = 0;
		for(int i=0; i<b.size(); i++){
			if(b.get(i).size()!= 0){
				result[counter] = i;
				counter++;
			}
		}
		System.out.println("result: "+ result.length);
		return result;
	}
}
